1. Field of the Invention
The present invention relates to modular exponentiation and, in particular, to modular exponentiation using the Chinese Residue Theorem (CRT).
2. Description of the Related Art
Before the RSA crypto-system will be explained in greater detail, some basic concepts of cryptography will be summarized. In general, we distinguish between symmetrical encrypting methods, which are also referred to as secret key encrypting methods, and public key encrypting methods, which are also referred to as encrypting methods having a public key.
A communication system having two parties which use an encryption with a symmetrical key can be described as follows. The first party communicates its encryption key via a safe channel to the second party. Subsequently, the first party encrypts the secret message by means of the key and transfers the encrypted message via a public or non-safe channel to the second party. The second party then decrypts the encrypted message using the symmetrical key having been communicated to the second party via the safe channel. A considerable problem in such encrypting systems is to provide an efficient method for exchanging the secret keys, i.e. for finding a safe channel.
An asymmetrical encryption in contrast takes place as follows. One party who wants to obtain a secret message communicates its public key to the other party, i.e. the party from which it wants to obtain a secret message. The public key is communicated via a non-safe channel, i.e. via a “public” channel.
The party who wants to send a secret message receives the public key of the other party, encrypts the message using the public key and sends the encrypted message again via a non-safe channel, i.e. via a public channel, to the party from which the public key comes. Only that party having produced the public key is able to provide a private key to decrypt the encrypted message. Not even the party having encrypted its message using the public key is able to decrypt the message. An advantage of this concept is that no safe channel between the two parties, i.e. no secret key exchange, is required. The party having encrypted the message must not know the private key of the message recipient.
A physical analogy to the asymmetrical encryption concept or public key encryption concept is as follows. A metal box is considered, the lid of which is locked by a combination lock. Only that party who wants to obtain an encrypted message knows the combination. If the lock is left open and made available in public, every party who wants to transmit a secret message can put this message into the metal box and close the lid. Only that party from which the box originates, however, knows the combination of the combination lock. It is only this party who is able to decrypt the message, i.e. to open the metal box again. Even that party who put the message into the box is no longer able to take the message out of it again.
Of importance for asymmetrical or public key encryption concepts is the basic mathematical problem, the solution of which for decrypting is nearly impossible using the public key, the solution of which is, however, easily possible knowing the private key. One of the best-known public key crypto-systems is the RSA crypto-system. The RSA crypto-system is described in “Handbook of Applied Cryptography”, Menezes, van Oorschot, Vanstone, CRC Press 1997, pages 285-291.
Subsequently, reference will be made to FIG. 3 to illustrate the RSA algorithm. The initial situation is that one communication partner encrypts a message m which the other communication partner has to decrypt again. The encrypting entity must at first, in step 200, obtain the public key (n, e) in order to be able to send the other party an encrypted message. Subsequently, the encrypting entity, in step 210, must present the message to be encrypted as an integer m, wherein m has to be within the interval from 0 to n−1. In step 220, which is the actual encrypting step, the encrypting entity must calculate the following equation:c=me mod n.
c is the encrypted message. It is then output in step 230 and transferred to the recipient of the encrypted message via a public channel which, in FIG. 2, is referred to by 240. The recipient, in step 250, receives the encrypted message c and, in step 260, which is the actual decrypting step, performs the following calculation:m=cd mod n.
It can be seen from FIG. 3 that only the public key (n, e) is required for encrypting but not the private key d, while when decrypting the private key d is required.
The question is how an attacker can violate an RSA crypto-system. He knows the public key, that is n and e. He could factorize the modulus n into a product of two prime numbers and then precisely calculate the secret key d like the key-generating authentic party has done. For this, the attacker would have to test all the possible prime number pairs p′, q′ to find the private key d sometime taking e into consideration as well. With small prime numbers p and q, this problem can be solved relatively easily by testing. If p and q, i.e. the modulus n equaling the product of p and q, become larger, the different possibilities for factorizing the modulus n will also increase extremely. This is the basis for the safety of the RSA system. Thus, it is obvious that a safe RSA crypto-system must use very long numbers which could, for example, have a length of 512, 1024 or even 2048 bits.
It can be seen from FIG. 3 that a modular exponentiation must be calculated for both an RSA encryption to produce an encrypted message c from a non-encrypted message m and for decrypting to generate a decrypted message m from an encrypted message c. This is made clear in FIG. 3 by steps 220 and 260. When calculating the modular exponentiation, the Chinese Residue or Remainder Theorem (CRT) is of special advantage when the integers used and, in particular, the modulus n, are long numbers. As has been explained, the safety of the RSA algorithm, however, is based on the fact that the integers are long.
The Chinese Residue Theorem is described in “Handbook of Applied Cryptography” mentioned above on page 610 and the following pages. The Chinese Residue Theorem, in particular in its form known as the Garner's algorithm, is based on the idea of splitting the modular exponentiation with the modulus n into two modular exponentiations of second sub-moduli p, q, wherein the sub-moduli p, q are prime numbers, and wherein the product of them results in modulus n. A modular exponentiation with a long modulus is thus split into two modular exponentiations having shorter sub-moduli (typically having half the length). This method is of advantage in that calculating units having only half the length are required or that, when the length of the calculating unit remains the same, numbers which have double the length can be used, which results in a more favorable relation of safety and chip area, i.e., in general in an improved relation of performance and price.
The Chinese Residue Theorem, applied to the modular exponentiation described, is as follows. At first, two prime numbers pq which should, if possible, have an equal length and the product p×q of which results in the modulus n, are calculated. Subsequently, a first auxiliary quantity dp is calculated as follows:dp=d mod(p−1)
Then, a second auxiliary quantity dq is calculated:dq=d mod(q−1)
Subsequently, a third auxiliary quantity Mp is calculated:Mp=cdp mod p
Another auxiliary quantity Mq is calculated as follows:Mq=cdq mod q
In a final summarizing step, the result of the modular exponentiation, i.e. in the present example, the plain text message m, is calculated as follows, assuming c to be the encrypted message:m=Mq+[(Mp−Mq)×q−1 mod p]×q
It can be seen from the above illustration of the Chinese Residue Theorem that a modular exponentiation with a long modulus n has been split into two modular exponentiations with sub-moduli p, q having half the length and that, in a last step for calculating the plain text message m, a summarizing operation is performed, in which the multiplicative inverse q−1 in relation to a sub-modulus p is required. Since the sub-modulus p is shorter than the original modulus n, the calculation of the multiplicative inverse q−1, such as, for example, using the extended Euclidian algorithm, is possible with a justifiable calculating complexity.
Although the usage of the Chinese Residue Theorem reduces the calculating time efficiency and the chip area consumption of a safety IC, respectively, the Chinese Residue Theorem has problems concerning attacks on the cryptography system, such as, for example, so-called side channel attacks, power analyses or fault attacks. An attacker could perform such attacks on the algorithm to “crack” the private key d.
In the case of an RSA encryption, i.e. when an encrypted message c is to be calculated from the plain text message, the safety problem is not that evident since, for encrypting a message, only the public key e is used anyway. The problem, however, occurs when using RSA as a signature algorithm.